  IOI. 13 (Harta). Figura de mai jos arata harta unui castel de forma
dreptunghiulara. Scrieti un program care determina:
  i) Cte camere are castelul; se considera ca exista totdeauna cel putin
doua camere.
 ii) Suprafata celei mai mari camere.
iii) Ce perete poate fi nlaturat pentru a obtine o camera ct mai mare.
Intrare: un set de date de intrare este format din:
- pe prima linie, doua numere care reprezinta marimea castelu-lui pe
orizontala respectiv pe verticala;
aceasta marime este data prin numarul de module ce pot fi desfasurate pe
fiecare latura.
- pe urmatoarele linii, fiecare modul este caracterizat de un numar
n(0n15), format prin nsumarea cifrelor 1 (daca modulul este delimitat
n partea de vest printr-un perete), 2 (daca are perete spre nord), 4
(perete la est), 8 (perete la sud). Peretii interiori sunt astfel definiti
de doua ori. Ordinea de definire a modulelor este cea data n exemplu.
Iesire: raspunsul va fi dat pe trei linii:
  i) numarul de camere;
 ii) aria celei mai mari camere (socotita n numar de module);
iii) o reprezentare sugestiva a peretelui care trebuie eliminat (n caz ca
sunt mai multe solutii posibile, se cere una din ele).

Exemplu: Pentru castelul definit de harta


fisierul de intrare va fi:
4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
iar o iesire posibila:
5
9
4 1 E
Aici, peretele care se poate elimina apartine modulului de pe a patra linie
si prima coloana, n partea de est.
=============================================
Solutia 1 (Mihai Stroe)

    Problema este simpla si cere aplicarea algoritmului clasic de umplere
  pentru o suprafata. Punctul 1 se realizeaza umplind din prima pozitie
  care nu a fost deja marcata camera care contine pozitia respectiva, cu
  numarul ei de ordine. Punctul 2 se realizeaza numarind elementele din
  fiecare camera, conform marcajului anterior, si obtinind apoi o alta
  matrice care contine pe pozitia (i,j) numarul de elemente din camera
  care include (i,j).
  Punctul 3 se rezolva prin calcularea pentru fiecare perete a sumei
  suprafetelor camerelor pe care le desparte si gasirea maximului. Se
  considera numai pereti care despart camere diferite. Se foloseste noua
  matrice obtinuta la punctul anterior.

var a,map,north,south,east,west:array[1..100,1..100]of byte;
    x,y,z,nr,nopt,i,j,k,l,m,n:longint;
    s:string;
    fi:text;

procedure readdata;
begin
  write('Type input file name ');
  readln(s);
  assign(fi,s);
  reset(fi);
  readln(fi,m,n);
  for i:=1 to m do
      begin
        for j:=1 to n do
            read(fi,map[i,j]);
        readln(fi);
      end;
  close(fi);
end;

procedure fill(i,j:byte);
begin
  if a[i,j]<>0 then exit;
  a[i,j]:=k;
  if north[i,j]=0 then fill(i-1,j);
  if south[i,j]=0 then fill(i+1,j);
  if west[i,j]=0 then fill(i,j-1);
  if east[i,j]=0 then fill(i,j+1);
end;

procedure solve;
begin
  for i:=1 to m do
      for j:=1 to n do
          begin
            if map[i,j] mod 2=1 then west[i,j]:=1;
            if map[i,j] div 2 mod 2=1 then north[i,j]:=1;
            if map[i,j] div 2 div 2 mod 2=1 then east[i,j]:=1;
            if map[i,j] div 2 div 2 div 2 mod 2=1 then south[i,j]:=1;
          end;
  k:=0;
  for i:=1 to m do
      for j:=1 to n do
          if a[i,j]=0 then
             begin
               inc(k);
               fill(i,j);
             end;
  writeln(k);
  nopt:=0;
  for l:=1 to k do
      begin
        nr:=0;
        for i:=1 to m do
            for j:=1 to n do
                if a[i,j]=l then inc(nr);
        if nr>nopt then nopt:=nr;
        for i:=1 to m do
            for j:=1 to n do
                if a[i,j]=l then map[i,j]:=nr;
      end;
  writeln(nopt);
  nopt:=0;
  x:=0;
  y:=0;
  z:=0;
  for i:=1 to m-1 do
      for j:=1 to n-1 do
          begin
            if a[i,j]<>a[i+1,j] then
            if map[i,j]+map[i+1,j]>nopt then begin nopt:=map[i,j]+map[i+1,j];x:=i;y:=j;z:=1;end;
            if a[i,j]<>a[i,j+1] then
            if map[i,j]+map[i,j+1]>nopt then begin nopt:=map[i,j]+map[i,j+1];x:=i;y:=j;z:=2;end;
          end;
  write(x,' ',y,' ');
  if z=1 then write('s') else write('e');
end;

begin
  readdata;
  solve;
end.
---------------------------------------
Solutia 2 (Catalin Francu)
program Harta;
{$B-,I-,R-,S-}
const NMax=140;
      West=$01;
      North=$02;
      East=$04;
      South=$08;
type RoomType=record
                W:Byte;
                Index:Integer;
              end;
     MazeType=array[1..NMax,1..NMax] of RoomType;
     IntegerVector=array[1..NMax*NMax] of Integer;
var A:MazeType;
    M,N,NRooms:Integer;
    Size:^IntegerVector; { Size[i] = Marimea camerei cu indicele i }

procedure ReadData;
var FileName:String;
    i,j:Integer;
begin
  Write('Numele fisierului de intrare: ');ReadLn(FileName);
  Assign(Input,FileName);Reset(Input);
  ReadLn(M,N);
  for i:=1 to M do
    begin
      for j:=1 to N do
        with A[i,j] do
          begin
            Read(W);
            Index:=0;
          end;
      ReadLn;
    end;
  Close(Input);
  NRooms:=0;
  New(Size);
end;

procedure Fill(X,Y:Integer);
begin
  with A[X,Y] do
    if Index=0 then begin
                      Inc(Size^[NRooms]);
                      Index:=NRooms;
                      if W and West=0 then Fill(X,Y-1);
                      if W and North=0 then Fill(X-1,Y);
                      if W and East=0 then Fill(X,Y+1);
                      if W and South=0 then Fill(X+1,Y);
                    end;
end;

procedure MakeRooms;
var MaxSize,i,j:Integer;
begin
  MaxSize:=0;
  for i:=1 to M do
    for j:=1 to N do
      if A[i,j].Index=0
        then begin
               Inc(NRooms);
               Size^[NRooms]:=0;
               Fill(i,j);
               if Size^[NRooms]>MaxSize then MaxSize:=Size^[NRooms];
             end;
  WriteLn(NRooms);
  WriteLn(MaxSize);
end;

procedure FindWall;
var MaxSum,i,j,X,Y,Dir:Integer;
begin
  MaxSum:=0;
  { Peretii verticali }
  for i:=1 to M do
    for j:=1 to N-1 do
      if (A[i,j].Index<>A[i,j+1].Index)
        and (Size^[A[i,j].Index]+Size^[A[i,j+1].Index]>MaxSum)
        then begin
               MaxSum:=Size^[A[i,j].Index]+Size^[A[i,j+1].Index];
               X:=i;
               Y:=j;
               Dir:=East;
             end;
  { Peretii orizontali }
  for i:=1 to M-1 do
    for j:=1 to N do
      if (A[i,j].Index<>A[i+1,j].Index)
        and (Size^[A[i,j].Index]+Size^[A[i+1,j].Index]>MaxSum)
        then begin
               MaxSum:=Size^[A[i,j].Index]+Size^[A[i+1,j].Index];
               X:=i;
               Y:=j;
               Dir:=South;
             end;
  Write(X,' ',Y,' ');
  case Dir of
    West:WriteLn('W');
    North:WriteLn('N');
    East:WriteLn('E');
    South:WriteLn('S');
  end;
end;

begin
  ReadData;
  MakeRooms;
  FindWall;
end.
-----------------------
Solutie Vlad Atanasiu
Program:
uses crt,graph;
type leg=^modul;
     modul=record
           x,y,tip:byte;
           urm:leg;
           end;
     legf=^figura;
     figura=record
            arie:integer;
            lista:leg;
            urm:legf;
            end;
     sol=record
         x,y:integer;
         c:char;
         end;
var fprima,fstart,fcurent:legf;
    max_arie,camere,a,b,i,j:integer;
    m,tmp:leg;
    solutie:sol;
    g:array[1..100,1..100] of integer;

procedure analizeaza(x1,y1,x2,y2:integer);
{ analizeaza casutele aflate la x1,y1 si x2,y2, care au un zid intre ele; daca
  fac parte din camere diferite, calculeaza aria maxima si propune solutia }
var gasit1,gasit2:boolean;
    arie:integer;
    f1,f2:legf;
begin
fcurent:=fstart;
gasit1:=false;
gasit2:=false;
arie:=0;
while not(gasit1 and gasit2) do
      begin
      tmp:=fcurent^.lista;
      while tmp<>nil do
            begin
            if (not gasit1) and (tmp^.x=x1) and (tmp^.y=y1) then
               begin
               gasit1:=true;
               arie:=arie+fcurent^.arie;
               f1:=fcurent;
               end
            else if (not gasit2) and (tmp^.x=x2) and (tmp^.y=y2) then
                 begin
                 gasit2:=true;
                 arie:=arie+fcurent^.arie;
                 f2:=fcurent;
                 end;
            if (tmp^.urm<>nil) and (tmp^.urm^.x>11) then
               readln;
            tmp:=tmp^.urm;
            end;
      fcurent:=fcurent^.urm;
      end;
if (f1<>f2) and (arie>max_arie) then
   begin
   max_arie:=arie;
   solutie.x:=x1;
   solutie.y:=y1;
   if x1>x2 then solutie.c:='W'
   else solutie.c:='S';
   end;
end;

function vecini(a,b:modul):boolean;
{ intoarce true daca doua module sunt legate (nu au perete intre ele) }
var r:boolean;
begin
r:=false;
if a.y=b.y then
   begin
   if (a.x=b.x-1) and ((a.tip and 4)<>4) then r:=true;
   if (a.x=b.x+1) and ((b.tip and 4)<>4) then r:=true;
   end
else if a.x=b.x then
        begin
        if (a.y=b.y-1) and ((b.tip and 2)<>2) then r:=true;
        if (a.y=b.y+1) and ((a.tip and 2)<>2) then r:=true;
        end;
vecini:=r;
end;

function in_figura(c:legf;m:leg):boolean;
{ intoarce true daca m are vecini in figura c }
var ct:leg;
begin
ct:=c^.lista;
while (ct<>nil) and (not vecini(m^,ct^)) do
      ct:=ct^.urm;
in_figura:=(ct<>nil);
end;

begin
clrscr;
assign(input,'input.i13');
{assign(output,'op');
rewrite(output);}
reset(input);
readln(input,a);
readln(input,b);
fstart:=nil;
for i:=1 to a do
    begin
    for j:=1 to b do
        begin
        new(m);
        read(input,m^.tip);
        m^.x:=j;
        m^.y:=i;
        m^.urm:=nil;
        fprima:=nil;
        fcurent:=fstart;
        g[j,i]:=m^.tip;
        while fcurent<>nil do
              begin
              if in_figura(fcurent,m) then
                 if fprima=nil then
                    begin
                    { daca este prima figura in care este intalnit atunci il
adauga la figura }
                    fprima:=fcurent;
                    tmp:=fprima^.lista;
                    while tmp^.urm<>nil do tmp:=tmp^.urm;
                    m^.urm:=fcurent^.lista;
                    fcurent^.lista:=m;
                    inc(fcurent^.arie);
                    end
                 else
                    begin
                    { daca nu este prima figura in care are vecini }
                    { adauga la fprima }
                    tmp^.urm:=fcurent^.lista;
                    while tmp^.urm<>nil do tmp:=tmp^.urm;
                    fprima^.arie:=fprima^.arie+fcurent^.arie;
                    { sterge fcurent }
                    fcurent^.lista:=nil;
                    fcurent^.arie:=0;
                    end;
              fcurent:=fcurent^.urm;
              end;
        if fprima=nil then
           begin
           { nu a fost adaugat la nici o figura }
           { creeaza o noua figura }
           new(fcurent);
           fcurent^.lista:=m;
           fcurent^.urm:=fstart;
           fstart:=fcurent;
           fstart^.arie:=1;
           end;
        end;
    readln(input);
    end;
max_arie:=0;
fcurent:=fstart;
camere:=0;
while fcurent<>nil do
      begin
      if fcurent^.arie>max_arie then max_arie:=fcurent^.arie;
      if fcurent^.arie>0 then inc(camere);
      fcurent:=fcurent^.urm;
      end;
writeln(' Camere : ',camere);
writeln(' Arie maxima : ',max_arie);
max_arie:=0;
for i:=1 to a do
    for j:=1 to b do
        begin
        { testarea se face numai pentru peretii din dreapta si jos, daca
exista }
        if (i<a) and (g[j,i] and 8=8) then analizeaza(j,i,j,i+1);
        if (j<b) and (g[j,i] and 4=4) then analizeaza(j,i,j+1,i);
        end;
writeln(' Poate fi eliminat peretele ',solutie.x,' ',solutie.y,' ',solutie.c);
end.
-------------------------------------------------
